Contents

1. 1. 总结：

　　在java中，RandomAccess是标志性接口，不需要任何实现，只是用来表明这个类可以随机存取，对于ArrayList来说也就标志着其数据元素之间没有关联，即两个位置相邻的元素之间没有相互依赖和索引关系，可以随机访问和存储。

现在来看个求和的例子：

public static int average1(List<Integer> list){
	int sum = 0;
	for(int i : list){
		sum += i;
	}
	return sum / list.size();
}

public static int average2(List<Integer> list){
	int sum = 0;
	for(int i = 0; i < list.size(); i++){
		sum += list.get(i);
	}
	return sum / list.size();
}

public static void main(String[] args){
    
	int stuNum = 80 * 1000;
	Random rand = new Random();
	List<Integer> scores = new ArrayList<Integer>(stuNum);
	for(int i = 0; i < stuNum; i++){
		scores.add(rand.nextInt(150));
	}
	long start = System.currentTimeMillis();
	System.out.println("平均分是： " + average1(scores));
	System.out.println("执行时间是 ：" + (System.currentTimeMillis() - start) + "ms");
	
	long start2 = System.currentTimeMillis();
	System.out.println("平均分是： " + average2(scores));
	System.out.println("执行时间是 ：" + (System.currentTimeMillis() - start2) + "ms");
	
}

• Foreach语法是iterator(迭代器)的变形用法，也就是说上面的foreach与下面的等价：

  for(Iterator<Integer> i = list.iterator(); i.hasNext();)
  		sum += i.next();

　　为了使用迭代器就需要建立一种互相“知晓”的关系，此处使用foreach遍历可能会稍微耗时一点。(但不知为什么实际运行的时候两个方法对于ArrayList求和得出的时间都是10~15ms左右，我猜可能是java现在对这方面底层有优化吧，但对于可随机访问的还是推荐使用get()方法)

　　但对于两个元素本来就是有关联的，使用foreach效率会更高一些。

将上面例子的List scores = new ArrayList(stuNum);换成：
List scores = new LinkedList();在来

看看结果：

平均分： 74
执行时间是： 17ms
平均分： 74
执行时间是： 4089ms

这里对于无法随机访问的LinkedList使用get()方法效率有蛮低。看看LinkedList的get源码：

public E get(int index){
	return entry(inedex).element;//entry方法查找指定下标的节点
}

// 获取双向链表中指定位置的节点    
    private Entry<E> entry(int index) {    
        if (index < 0 || index >= size)    
            throw new IndexOutOfBoundsException("Index: "+index+    
                                                ", Size: "+size);    
        Entry<E> e = header;    
        // 获取index处的节点。    
        // 若index < 双向链表长度的1/2,则从前先后查找;    
        // 否则，从后向前查找。    
        if (index < (size >> 1)) {    
            for (int i = 0; i <= index; i++)    
                e = e.next;    
        } else {    
            for (int i = size; i > index; i--)    
                e = e.previous;    
        }    
        return e;    
    }
性能损失就在这个方法里。

总结：

• 对于有RandomAccess接口的例如:ArrayList推荐用第二种方法遍历：sum += socres.get(i);

• 对于没有RandomAccess接口的例如:LinkedList 推荐用foreach语法来遍历

所以有个更好的方法：

public static int average(List<Integer> list){
	int sum = 0;
	if(list instanceof RandomAccess){
		//可以随机存取，则使用下标遍历
		for(int i = 0, size = list.size(); i < size; i++){
			sum += list.get(i);
		}
	}else{//有序存取，使用foreach语法遍历
		for(int i : list){
			sum += i;
		}
	}
	return sum / list.size();
}